package com.lw.leetcode.hash.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 310. 最小高度树
 * <p>
 * [[3,0],[3,1],[3,2],[3,4],[5,4]]
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/16 11:16
 */
public class FindMinHeightTrees {


    public static void main(String[] args) {
        FindMinHeightTrees test = new FindMinHeightTrees();
//        int[][] arr = {{3,0},{3,1},{3,2},{3,4},{5,4}};
//        int k = 6;

        int[][] arr = {{1, 0}, {1, 2}, {1, 3}};
        int k = 4;

//        int[][] arr = {{1, 0}};
//        int k = 2;

//        int[][] arr = {};
//        int k = 1;

        List<Integer> minHeightTrees = test.findMinHeightTrees(k, arr);
        System.out.println(minHeightTrees);
    }


    private Map<Integer, List<Integer>> map;

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {

        List<Integer> li = new ArrayList<>();
        if (n == 1) {
            li.add(0);
            return li;
        }

        map = new HashMap<>(n << 1, 1);
        for (int[] edge : edges) {
            map.computeIfAbsent(edge[0], v -> new ArrayList<>()).add(edge[1]);
            map.computeIfAbsent(edge[1], v -> new ArrayList<>()).add(edge[0]);
        }
        List<Integer> list = find(-1, 0);
        list = find(-1, list.get(0));
        int max = list.size();
        if ((max & 1) == 0) {
            li.add(list.get((max - 1) >> 1));
        }
        li.add(list.get((max) >> 1));
        return li;
    }

    private List<Integer> find(int last, int index) {
        List<Integer> list = map.get(index);
        int count = 0;
        List<Integer> items = null;
        for (int value : list) {
            if (value == last) {
                continue;
            }
            List<Integer> li = find(index, value);
            if (li.size() > count) {

                count = li.size();
                items = li;
            }
        }
        if (items == null) {
            items = new ArrayList<>();
        }

        items.add(index);
        return items;
    }

//    private int find(int[] arr, int last, int index) {
//        List<Integer> list = map.get(index);
//        int count = 0;
//        for (int value : list) {
//            if (value == last) {
//                continue;
//            }
//            count = Math.max(find(arr, index, value) + 1, count);
//        }
//        arr[count] = index;
//        return count;
//    }


    public List<Integer> findMinHeightTrees2(int n, int[][] edges) {
        List<Integer> ans = new ArrayList<>();
        if (n == 1) {
            ans.add(0);
            return ans;
        }
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        /* 找到与节点 0 最远的节点 x */
        int x = findLongestNode(0, parent, adj);
        /* 找到与节点 x 最远的节点 y */
        int y = findLongestNode(x, parent, adj);
        /* 求出节点 x 到节点 y 的路径 */
        List<Integer> path = new ArrayList<>();
        parent[x] = -1;
        while (y != -1) {
            path.add(y);
            y = parent[y];
        }
        int m = path.size();
        if (m % 2 == 0) {
            ans.add(path.get(m / 2 - 1));
        }
        ans.add(path.get(m / 2));
        return ans;
    }

    public int findLongestNode(int u, int[] parent, List<Integer>[] adj) {
        int n = adj.length;
        Queue<Integer> queue = new ArrayDeque<Integer>();
        boolean[] visit = new boolean[n];
        queue.offer(u);
        visit[u] = true;
        int node = -1;

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            node = curr;
            for (int v : adj[curr]) {
                if (!visit[v]) {
                    visit[v] = true;
                    parent[v] = curr;
                    queue.offer(v);
                }
            }
        }
        return node;
    }


}
